1. Technical Field of the Invention
The present invention generally relates to arbitration techniques. More particularly, and not by way of any limitation, the present invention is directed to a binary tree arbitration (BTA) system and method designed to provide fairer servicing.
2. Description of Related Art
The use of arbitration is well-known as a resolution mechanism among a plurality of units contending for a common resource. For example, servers associated with input and output ports of a network element must first compete in order to establish appropriate traffic paths across a switching fabric before data can be transported between a selected input port and an output port. Since arbitration times can take a significant portion of a scheduling process, it is highly desirable to implement a faster arbitration scheme where massive throughput rates are required.
Other concerns also arise in environments involving a selection of one among several weighted units. Ideally, any arbitration technique employed in such a scenario should result in a selection probability distribution that matches the units' relative weights in accordance with established Generalized Processor Sharing (GPS) principles. When applied to scheduling processes in a network element, this problem translates into arbitrating among requests generated by various input queues that are differentiated based on a number of Quality of Service (QoS) parameters.
Known solutions for supporting fast arbitrations (i.e., where arbitration iterations can be executed in a few clock cycles) involve arbiters whose structure and logic are implemented in hardware. Such hardware implementations of round-robin arbiters (RRAs) and binary tree arbiters (BTAs) are exemplary. Whereas these solutions are deemed to be generally adequate in terms of their scalability and relatively simpler design, certain deficiencies and shortcomings persist. First, although the existing hardware-based RRAs and BTAs are fast, they are not fair with respect to servicing requests from differentiated traffic classes. Typically, fairness can only be implemented at the cost of computational complexity, which not only necessitates expensive hardware but results in slower arbitration times as well. Thus, the price/performance ratios of today's arbiters are not entirely satisfactory in QoS-aware networks.
Further, the current RRA and BTA techniques are inherently unfair in the case of polarized traffic where a portion of the contending units disproportionately generate service requests relative to the other units. In the context of telecommunications networks, this condition introduces longer access delays and queue lengths, in addition to packet loss due to full buffers. Relatedly, where the traffic is classified into multiple priorities, low priority queues may have to contend with buffer starvation which results in degraded service.